The present invention is in the general field of memory management and concerns more specifically garbage collection (GC) for computer languages and computer systems.
1. Mordechai Ben-Ari. On-the-fly garbage collection: New algorithms inspired by program proofs. In M. Nielsen and E. M. Schmidt, editors, Automata, languages and programming. Ninth colloquium (Aarhus,Denmark) pages 14-22, New York, Jul. 12-16, 1982. Springer-Verlag.
2. Mordechai Ben-Ari. Algorithms for on-the-fly garbage collection. ACM Transactions on Programming Languages and Systems, 6(3):333-344, July 1984.
3. Alan Demers, Mark Weiser, Barry Hayes, Daniel G. Bobrow, and Scott Shenker. Combining generational and conservative garbage collection: Framework and implementations. in Conference Record of the Seventeenth Annual ACM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices, January 1990. ACM Press,pages 261-269.
4. Edsgar W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten and E. F. M. Steffens. On-the-fly garbage collection: An exercise in cooperation. In Lecture Notes in Computer Science, No. 46, Springer-Verlag, New York, 1976.
5. Edsgar W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten and E. F. M. Steffens. On-the-fly garbage collection: An exercise in cooperation. Communications of the ACM, 21 (11): 965-975, November 1978.
6. D. Doligez and G. Gonthier. Portable, unobtrusive garbage collection for multiprocessor systems. In Conference Record of the Twenty-first Annual ACM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices. ACM Press, 1994, pages 113-123.
7. D. Doligez and X. Leroy. A concurrent generational garbage collector for a multi-threaded implementation of ML. In Conference Record of the Twentieth Annual ACM Symposium on Principles of Programming Languages, ACM SIGPLAN Notices. ACM Press, January 1993.
8. David Gries.
An exercise in proving parallel programs correct. Communications of the ACM, 20(12):921-930, December 1977.
9. P. Hudak, R. M. Keller. Garbage Collection and Task Deletion in Distributed Systems. In ACM Symposium on Lisp and Functional Programming, pp. 168-178, Pittsburgh, Pa. August 1982.
10. R. E. Jones and R. D. Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. John Wiley  and Sons, July 1996.
11. H. T. Kung and S. W. Song. An efficient parallel garbage collection system and its correctness proof. In IEEE Symposium on Foundations of Computer Science, pages 120-131. IEEE Press, 1977.
12. L. Lamport. Garbage collection with multiple processes: an exercise in parallelism. In Proceedings of the 1976 International Conference on Parallel Processing, pages 50-54, 1976.
13. H. Lieberman and C. E. Hewitt. A Real Time Garbage Collector Based on the Lifetimes of Objects. Communications of the ACM, 26(6), pages 419-429, 1983.
14. Guy L. Steele. Multiprocessing compactifying garbage collection. Communications of the ACM, 18(9):495-508, September 1975.
15. Guy L. Steele. Corrigendum: Multiprocessing compactifying garbage collection. Communications of the ACM, 19(6):354, June 1976.
Garbage collectors free the space held by unreachable (dead) objects so that this space can be reused in future allocations.
An on-the-fly garbage collector, i.e., a collector that reclaims unused space in parallel to the running program without stopping it for the collection is a fascinating theoretical idea with important benefits in practice. In particular, in many server platforms the actual operation of stopping all parallel threads in order to do a garbage collection task is a high cost time consuming operation. The reason is that the threads cannot be stopped at any point and thus there is a relatively long wait until the last (of many) threads reaches a point where it may stop.
The study of on-the-fly garbage collectors was initiated by Steeles and Dijkstra et. al. [14, 15, 4] and was continued in a series of many papers (see for example [5,8,1,2,11 and 12] culminating in the Doligez-Gonthier-Leroy (DGL) collector [6,7].
The specified collectors are of the so called mark and sweep collector type. In these type of collectors, there is normally a first step, in which the live objects in the heap are marked and there is a second step in which the unmarked objects are xe2x80x9csweptxe2x80x9d, i.e., reclaimed for future use.
The trace of live objects is done with a 3-color scheme: Objects are white if they have not been traced, they are marked gray if they have been traced but their immediate children have not been traced yet, and they are marked black if they have been traced and their immediate children have been traced as well. The trace proceeds step by step by taking a gray object, marking it black and marking gray all its white children.
The fact that the collector works xe2x80x9con-the-flyxe2x80x9d makes its life harder. Thus, while it is scanning the heap, the reachability graph is changed by the user program concurrently. If the collector uses this naive search, it may miss some live items. If, for example, (see FIG. 1) the user program moves a white node (1) from being reference by a gray object (2) (i.e., whose children (3 and 4) have not yet been traced) to being referenced by a black object (5) (whose sons (6, 7) will not be traced any more), then the white object (1) (and its sons, if any) may not be traced.
To solve this problem and let the collector spot all live objects during the trace, the program threads help the collector through a write barrier. During the time that the collector performs the tracing of the heap, whenever a pointer is modified from pointing to an object A into pointing to object B, either A or B are marked gray by the modifier thread (by the embodiment of FIG. 1 object (1) is marked gray either when the connection to (5) is created or when reference from (2) is erased). Choosing which of the objects to mark is up to the specific algorithm. In some algorithms both A and B may be marked gray. This operation of the program is sometimes called the xe2x80x9cwrite barrierxe2x80x9d or the xe2x80x9cupdate protocolxe2x80x9d.
Another issue is how to color newly allocated objects during the collection. A solution to the latter problem is sometimes called the xe2x80x9ccreate protocolxe2x80x9d.
The specific details of an on-the-fly algorithm are well documented in the literature and therefore will not be expounded upon herein.
Turning now to generational garbage collection, the idea was introduced by Lieberman and Hewitt [13]. Generational garbage collectors rely on the assumption that many objects die young. The heap is partitioned into two parts: the young generation and the old generation. New objects are allocated in the young generation which is collected frequently. (See FIG. 2)
Young objects that survive several collections are xe2x80x9cpromotedxe2x80x9d to the older generation. Since the young generation is kept small, most collections are fast and do not stall the application for too long, giving rise to the following advantages:
1. Most collections are fast and efficient: they concentrate on the young part where a high percentage of garbage is normally found.
2. The young generation is frequently collected and therefore can be frequently reused.
3. The collector uses a smaller working set since most collections only scan a small part of the young generation.
4. The specified advantages give rise to an overall system behavior with less paging: the collector traces through less pages and the program keeps a small working set since the heap is reused.
Traditionally, generational collections partition the heap into the generations in a physical sense. Namely, to promote an. object from the young generation to the old generation, the object has to be moved from the young part of the heap to the old part of the heap. Reverting for a moment to on-the-fly collectors it is not recommended to move objects in the heap (by the collector) concurrently with the run of the program since a given object may be used by the program whilst being removed by the collector bringing about obvious undesired results. Whilst the moving object conflict may be resolved by utilizing known per se synchronization primitives, the latter pose an undue overhead on the overall performance of the program/collector.
There follows a brief description of a known per se generational collector that does not move the objects in the heap.
As will be explained below, the latter concept is used by the system and method of the invention. It should be noted, however, that the invention is by no means bound by this particular example.
Thus, Demers et. al. [3] presented a generational collector that does not move the objects in the heap (hereinafter mark and sweep). Their motivation was to allow generational collection when a conservative collection is required.
There follows a brief review of the specified non-moving generational collection technique. The description is focused in a version of the algorithm which is defined in the paper as xe2x80x9cthe sticky bitsxe2x80x9d. At first the algorithm is described and then the issue of why it constitutes a generational collector is addessed. The description focuses on a xe2x80x9cstop the worldxe2x80x9d collector, i.e., it is assumed that when the collector is run, the program threads (mutators) are stopped. (Of course, in the system and method of the invention the latter stipulation does not apply). It should be noted that the description bellow does not follow Demers exactly. Thus, terminology and concepts that are not mentioned in Demers and yet are useful for understanding the underlying concept of the invention, e.g. xe2x80x9ccolorsxe2x80x9d is used.
For a better understanding of the foregoing attention is now directed to FIG. 2 showing a generalized schematic illustration of a heap partitioned to generations. It is assume that, at first stage, memory object (29) and pointer (26) (marked in dashed lines) do not exist and accordingly the heap consists of only objects (23, 24, 27 and 28) Thus, in a mark and sweep algorithm, the collector starts with all allocated objects being white,((23), (24), (27) and (28)), and during the xe2x80x9cmarkxe2x80x9d stage, it marks in black all objects that are reachable from the roots by a path of pointers. (In FIG. 2: (23), (24) and (27)).
First, all objects that are referenced by the stack and registers (the roots) are grayed. Then, all live objects are traced in the following way:
if there is a gray object A, then A gets black color, and for any white object B referenced by A, B gets gray color. The latter series of steps constitute a first form of tracing which continues until there are no more gray objects. All live objects are-then black and garbage objects are white. In the embodiment of FIG. 2, only object (28) is white upon completion of the algorithm
After the mark phase is completed and all live objects are colored black, the sweep phase reclaims white objects and re-colors black objects white in preparation for the next garbage collection cycle. This collection which starts with all objects white, marks all live objects, and reclaims all unmarked objects, is called full collection, since all the heap is collected.
In the method of [3], a so-called partial collection is also allowed. Thus, at the end of each collection (while sweeping), black objects are left black and accordingly at the start of the next partial collection many of the live objects in the heap are black. (This is the reason for the name of the method: the bits that mark the object black stick to it, that is, they are not cleared at sweep time.) By the particular example of FIG. 2, objects (23), (24) and (27) remain black.
During the normal operation time, the program threads (also called mutators), record all pointer modifications. To do that, the heap is partitioned into cards, and each card has an associated dirty-bit indicating whether this card was modified since the last collection. A detailed discussion of the known per se card marking can be found in [10]. When a mutator modifies a pointer, (e.g. pointer (26) is added from object (27) to a new object, (29), it marks the card to which the pointer belongs as xe2x80x9cdirtyxe2x80x9d (recording updates is not needed for a full collection).
Thus, all pointers (by this example (26)) that were modified between the collection are on dirty cards. Alternatively, it is possible to keep a dirty bit per object and mark each object as being dirty or not, i.e. mark object (24) as dirty.
A partial collection operates, typically, as follows:
Marking starts with the regular roots marking plus a marking of all white objects referenced from black objects on dirty cards.
In the case that a dirty bit is kept for each object, then all the objects that are referenced by dirty black objects are marked gray. By the specific example of FIG. 2, the marking starts from the root and from the black object (24), which has its dirty bit set. All dirty bits are then cleared.
After this initial marking, a standard tracing is executed: for each object marked gray in the manner specified, mark it black and all its"" white descendants gray. This implies that the tracing does not go through black (marked) objects. Namely, when a black object with its dirty bit reset is encountered, its descendants are not traced.
By the embodiment of FIG. 2, if objects (23) and (27) had descendants, the latter would not have been traced since their respective dirty bits are reset. In contrast, object (24) is traced (due to the fact that its dirty bit is set), and therefore, its son (29) is traced and subject to color change (from white through gray to black) in the manner specified.
After tracing, the heap is swept, i.e., all white objects are reclaimed. The marked objects are either unmarked for a next full collection, or remain marked for another partial collection.
Accordingly, it should be noted that in partial collection, despite the fact that black objects are not traced, the dirty bit assumes that xe2x80x9cblack objectsxe2x80x9d will be nevertheless, traced, and their descendant duly treated, i.e. assigned with the appropriate color. The net effect is that despite the partial collection, no living object is mistakenly reclaimed.
There follows now brief description for clarifying why the specified algorithm constitutes a generational collector.
In order to explain that, one should think of the black objects as being in the old generation and the white objects as being in the young generation. The part of the heap that is touched during the mark stage contains exactly the objects in the young generation plus the objects in the old generation required to mark inter-generational pointers.
The young generation here contains all objects that were created after the last collection.
Note that all objects that survived the last collection must be black. Thus, the objects in the old generation are not traced.
Objects that are candidates for holding inter-generational pointers are traced. Similar to xe2x80x9cregularxe2x80x9d generational collection, all modified objects (or all objects on modified cards) must be scanned in order to find all inter-generational pointers (pointing from the old generation to the young generation). Thus, all marked objects on all dirty cards are scanned and inter-generational pointers are marked: i.e. pointers that point from old objects on dirty cards into the young generation. In the present case, these are dirty black objects. Finally, as always, tracing does not trace through the old generation since black objects are not traversed.
There is accordingly a need in the art to incorporate generations into on-the-fly collector so as to obtain a generational on-the-fly garbage collector which benefits from the advantages (as discussed above) of both conventional generational garbage collector and on-the fly collector.
According to the invention there is provided for the first time a generational on-the-fly collector. There is thus provided in accordance with the invention a method for performing garbage collection of memory objects in a memory heap, the method comprising the steps of:
(a) partitioning said heap or portion thereof into at least two generations; and
(b) applying substantiality on-the-fly garbage collection to memory objects in at least one from among said generations, whilst running at least one program thread.
In accordance with an aspect of the invention and as will be explained in greater detail below, the inter-generational value (e.g. dirty bit value) and identifier value (e.g. color value) associated with memory objects are manipulated so as to avoid races, e.g. by utilizing synchronization primitives or utilizing separated data structures for atomic write units.
In accordance with another aspect of the invention there is provided a technique for avoiding premature promotion, i.e. to keep for slightly longer the so created memory object in the young generation before they are promoted to older generation. As will be explained below, this is achieved by defining another unique color which is associated to newly created memory objects and which indicates that the specified memory object should not be reclaimed or promoted to older generation in this cycle of collection.
Accordingly, by this aspect, the invention provides for a method of the kind specified, wherein the manipulating step further utilizing a unique identifier value for avoiding pre-mature promotion of memory objects from a young generation to an older generation from among said at least two generations.
As will be explained in greater detail below, the utilization of a unique color in the manner specified may result in a race which may adversely affect the correctness of the proposed scheme. In order to avoid the specified undesired race, a so-called color toggling technique is utilized.
In accordance with another aspect of the invention, there is provided an ongoing technique which enables to delay the promotion of objects to older generations for predetermined time duration, e.g. in collection cycles (n being parameter).
The invention further provides for a computer system that includes memory for performing garbage collection of memory objects in a memory heap, the heap or portion thereof is partitioned into at least two generations; the system comprising:
at least one program thread running in said computer system;
a garbage collector for applying substantiality on-the-fly garbage collection to memory objects in at least one from among said generations, whilst running at least one of said program threads.
Still further, the invention provides for a computer system having a memory that includes data representative of memory objects in a memory heap; the memory heap or portion thereof is partitioned into at least two generations; the memory objects in at least one of said generations sustain after applying the specified garbage collection step.
The invention further provides for a computer system having a memory that includes data representative of memory objects in a memory heap; the memory heap or portion thereof is partitioned into at least two generations; said memory objects are associated with inter-generational values and identifier values for accomplishing garbage collection.